//
//  main.cpp
//  TestAdjacencyMatrix
//
//  Created by Ema on 2019/8/7.
//  Copyright © 2019年 Ema. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

bool isInCloseArray(int val, int * closeArray, int n);
//获取当前点最近的一个相邻点 返回下标
//需要排除已经找到过的点 路径点需要排除或者进行最短的路径对比 比如 0 - 4 4 - 0就不用看了
int getTheNearestCity(int* neighbour, int row, int n, int* closeArray)
{
    int tempVal = -1;
    int index = 0;
    int curVal = 0;
    for(int i = 0; i < n; ++i)
    {
        if(isInCloseArray(i, closeArray, n))
        {
            continue;
        }
        curVal = neighbour[row * n + i];
        if(curVal > 0)
        {
            if(tempVal == -1 || curVal < tempVal)
            {
                tempVal = curVal;
                index = i;
            }
        }
    }
    return index;
}


int getTheFarestCity(int* distance, int n)
{
    int tempVal = -1;
   
    for(int i = 0; i < n; ++i)
    {
        if (distance[i] > tempVal)
        {
            tempVal = distance[i];
        }
    }
    return tempVal;
}



bool isInCloseArray(int val, int * closeArray, int n)
{
    for(int i = 0; i < n; ++i)
    {
        if(closeArray[i] >= 0 && closeArray[i] == val)
        {
            return true;
        }
    }
    return false;
}

void showDistance(int* cityDistance, int n)
{
    for(int i = 0; i < n; ++i)
    {
        printf("%d ",cityDistance[i]);
    }
    printf("\n");
}


int main(int argc, const char * argv[]) {
    // insert code here...
    int n = 0;
    printf("please input input number of cities \n");
    scanf("%d",&n);
    if(n < 1 || n > 100)
    {
        printf("input number of cities must >= 1 and <= 100\n");
        return 0;
    }
    
    int size = sizeof(int) * (n * n);
    int* adjacencyMatrix = (int*)malloc(size);
    memset(adjacencyMatrix, 0, size);
    
    
    for(int i = 1; i < n; ++i)
    {
        for(int j = 0; j < i; ++j)
        {
            int tempVal = 0;
            scanf("%d", &tempVal);
            adjacencyMatrix[i * n + j] = tempVal;
            adjacencyMatrix[j * n + i] = tempVal;
            char v = getchar();
            if (v >= 'a' && v <= 'z')
            {
                //printf("is char \n");
                adjacencyMatrix[i * n + j] = -1;
                adjacencyMatrix[j * n + i] = -1;
            }
        }
    }
    
    
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            printf("%d ",adjacencyMatrix[i * n + j]);
        }
        printf("\n");
    }
    
    
    //开始计算最小连通路径
    int* cityPoints = (int*)malloc(sizeof(int) * n);
    memset(cityPoints, -1, sizeof(int) * n);
    
    //起始点到所有点距离的开销数组 之后要不断的更新该数组
    int* cityDistance = (int*)malloc(sizeof(int) * n);
    memcpy(cityDistance, adjacencyMatrix,sizeof(int) * n);
    
    showDistance(cityDistance, n);
    printf("\n");
    //set the start idx cityPoints[0] = 0;
    int idx = 0;
    int count = 0;
    while(count < n)
    {
        //取每一列 得到每一列或者每一行中最小的数开始
        //printf("%d\n",getTheNearestCity(adjacencyMatrix,i,n));
        cityPoints[count] = idx;
        idx = getTheNearestCity(adjacencyMatrix,idx,n, cityPoints);
        printf("idx = %d  ",idx);
        if(idx == 0)
        {
            break;
        }
        //更新距离数据
        for(int j = 1 ; j < n; ++j)
        {
            //临接点的距离
            int val = adjacencyMatrix[idx * n + j];
            //计算临接点到其他点距离 和 起始点直接到其他点距离的大小
            if(cityDistance[j] == -1 && val > 0)
            {
                cityDistance[j] = val + cityDistance[idx];
            }
            else if(val > 0 && (val + cityDistance[idx]) < cityDistance[j])
            {
                cityDistance[j] = val + cityDistance[idx];
            }
        }
        ++count;
        printf("the %d times   ",count);
        showDistance(cityDistance, n);
        printf("\n");
    }
    
    //最后输出最少需要多少时间 实际上就是最短路径中最大的值
    printf("need time = %d\n",getTheFarestCity(cityDistance, n));
    
    free(adjacencyMatrix);
    free(cityPoints);
    free(cityDistance);
    return 0;
}
